package Backtracking;

import java.util.ArrayList;
import java.util.List;

public class 组合总和3 {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> comb = new ArrayList<>();
    int len = 0;
    int target = 0;

    public List<List<Integer>> combinationSum3(int k, int n) {
        len = k;
        target = n;
        backTracking(1, 0);
        return res;
    }

    private void backTracking(int num, int sum) {
        if (sum > target) return;
        if (comb.size() == len) {
            if (sum == target) res.add(new ArrayList<>(comb));
            return;
        }
        for (int i = num; i <= Math.min((target - sum) / (len - comb.size()), 9 - (len - comb.size()) + 1); i++) {
            comb.add(i);
            sum += i;
            backTracking(i + 1, sum);
            sum -= i;
            comb.removeLast();
        }
    }
}
